﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.Schemes;
using Algoritmia.StateSpace;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Puzzles.Polyominoes
{
    public class PolyominoesStateSpace : 
        IReversibleForwardStateSpace<PolyominoesStateSpace.State,
                                     PolyominoesStateSpace.Decision>
    {
        #region Inner Classes
        public class State
        {
            public List<List<char>> Board;
            public int Freecells;
            public int Index;

            public State(string s)
            {
                int i = 0;
                Board = new List<List<char>>();
                foreach(var row in s.Split('\n'))
                {
                    Board.Add(new List<char>());
                    var array = row.ToCharArray();
                    for(int k = 0; k < array.Length; k++)
                    {
                        Board[i].Add(array[k]);
                    }
                    i++;
                }
                Freecells = (from row in Board
                              from cell in row
                              where cell == '.'
                              select cell).Count();
                Index = 0;
            }

            public override string ToString()
            {
                var sb = new StringBuilder();
                foreach(var row in Board)
                {
                    foreach(var cell in row)
                    {
                        sb.Append(cell);
                    }
                    sb.Append("\n");
                }
                return sb.ToString();
            }
        }

        public class Decision
        {
            public IEnumerable<Tuple<int, int>> Polyomino;
            public char Symbol;
            public int X;
            public int Y;

            public Decision(char symbol, IEnumerable<Tuple<int, int>> polyomino, int x, int y)
            {
                Symbol = symbol;
                Polyomino = polyomino;
                X = x;
                Y = y;
            }
        }
        

        #endregion

        private readonly string _board;
        private readonly Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int,int>>>>> _pieces;

        public PolyominoesStateSpace(string board, Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int,int>>>>> polyominoes)
        {
            _board = board;
            _pieces = polyominoes;
        }

        #region Implementation of IForwardStateSpace<State,Decision>

        public State Decide(State state, Decision decision)
        {
            var x = decision.X;
            var y = decision.Y;
            var cellsOcuppied = 0;
            foreach(var point in decision.Polyomino)
            {
                state.Board[point.Item2 + y][point.Item1 + x] = decision.Symbol;
                cellsOcuppied++;
            }
            state.Freecells -= cellsOcuppied;
            state.Index++;
            return state;
        }

        public IEnumerable<Decision> Decisions(State state)
        {
            if ( state.Index < _pieces.Count)
            {
                var tuple = _pieces[state.Index];
                char symbol = tuple.Item1;
                var polyominoes = tuple.Item2;
                foreach(var polyomino in polyominoes)
                {
                    for(int y = 0; y <  state.Board.Count;y++)
                    {
                        for(int x = 0; x < state.Board[y].Count; x++)
                        {
                            bool free = true;
                            foreach(var point in polyomino)
                            {
                                var i = point.Item1;
                                var j = point.Item2;
                                //Console.WriteLine(String.Format("Height: {0}, Length: {1}, y: {2}, x: {3}",state.Board.Count,state.Board[j+y].Count,j+y,i+x));
                                if ( j+y >= 0 && j+y < state.Board.Count && i+x >= 0 && i+x < state.Board[j+y].Count)
                                {
                                    if (state.Board[j + y][i + x] != '.')
                                    {
                                        free = false;
                                    }
                                }
                                else
                                {
                                    free = false;
                                }
                           
                            }
                            if ( free)
                            {
                                yield return new Decision(symbol,polyomino,x,y);
                            }
                        }
                    }
                }
            }

        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_board); }
        }

        public bool IsFinal(State state)
        {
            return state.Freecells == 0 && state.Index == _pieces.Count;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,Decision>

        public State Undo(State state, Decision decision)
        {
            var x = decision.X;
            var y = decision.Y;
            var newFreeCells = 0;
            foreach (var point in decision.Polyomino)
            {
                state.Board[point.Item2 + y][point.Item1 + x] = '.';
                newFreeCells++;
            }
            state.Freecells += newFreeCells;
            state.Index--;
            return state;
        }

        #endregion
    }

    public class PolyominoesSolver
    {
        private readonly BacktrackingEnumerator<PolyominoesStateSpace.State, PolyominoesStateSpace.Decision, string> _enumerator;
        private readonly Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int, int>>>>> _polyominoes;
        private readonly string _board;

        public PolyominoesSolver(string board,Lists.IList<Tuple<char, IEnumerable<IEnumerable<Tuple<int,int>>>>> polyominoes)
        {
            _board = board;
            _polyominoes = polyominoes;
            _enumerator =
                new BacktrackingEnumerator<PolyominoesStateSpace.State, PolyominoesStateSpace.Decision, string>(
                    (space, i, d, f) => f.ToString());
        }

        public string Solve()
        {
            var stateSpace = new PolyominoesStateSpace(_board, _polyominoes);
            return _enumerator.First(stateSpace);
        }
    }
}
